package main.Trie;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * <p>A tree structure which maps character strings to associated values. An AbstractTrie is
 * designed to allow for fast retrieval of values with String-based keys. As
 * such, this class only allows keys which are of type String.</p>
 *
 * <p>AbstractTrie extends AbstractMap and is therefore also a Map.</p>
 *
 * <p>This implementation does not permit null keys, null values, or keys that are
 * the empty string ("").</p>
 * 
 * <p> It is designed to be able to be extended such that you can extend both the Trie portion and
 * the TrieNode portion using generics. One must create a subclass of AbstractTrieNode<E>, lets call it
 * Node, and a subclass AbstractTrie<Node, E> for it to be used properly. If you need normal behavior,
 * see Trie.
 *
 * @author Brett McLean
 * @author Jared Hance
 * @param <E> the type of values to be stored by this Trie.
 * @see java.util.Map
 * @see main.Trie.Trie
 */

public abstract class AbstractTrie<N extends AbstractTrieNode<N, E>, E> extends AbstractMap<String, E> implements Serializable {

    protected transient N root;
    protected transient int size;

    /**
     * Creates a new empty Trie.
     */
    public AbstractTrie() {
        super();
        root = this.createNode();
        size = 0;
    }

    /**
     * Creates a new Trie, populating it with values from a Map.
     * @param map a Map the new Trie will draw its values from.
     */
    public AbstractTrie(Map<String, E> map) {
        super();
        root = this.createNode();
        putAll(map);
    }
    
    /**
     * Create a new empty node.
     * @return A new node.
     */
    public abstract N createNode();

    /**
     * Adds a key/value pair to the Trie. Null keys and null values are
     * not allowed.
     * @param keyParameter the key to add to the Trie.
     * @param value the value to associate with the key.
     * @return the object previously associated with the key. If this key
     * was not already in Trie, null is returned.
     */
    @Override
    public E put(String keyParameter, E value) {

        String key = keyParameter;

        /* Ignore ineligible keys */
        if (key == null || key.length() == 0 || value == null) {
            return null;
        }

        N currNode = root;
        N nextNode = null;

        /* Work down the Trie, inserting nodes where necessary. */
        while (key.length() > 0) {
            nextNode = currNode.findChild(key.charAt(0));
            if (nextNode == null) {
                nextNode = currNode.addChild(key.charAt(0));
            }
            currNode = nextNode;
            key = key.substring(1);
        }

        E returnThisObject = nextNode.getValue();

        nextNode.setValue(value);

        /* If the node didn't previously contain a value */
        if (returnThisObject == null) {
            size++;
        }

        return returnThisObject;
    }

    /**
     * Traverses the Trie and returns the value associated with the given key.
     * @param keyParameter the key to search against.
     * @return the object associated the given key. Returns null if there is
     * no entry associated with the given key.
     */
    public E get(String keyParameter) {

        String key = keyParameter;

        /* Ignore ineligible keys */
        if (key == null || key.length() == 0) {
            return null;
        }
        N currNode = root;
        while (key.length() > 0) {
            currNode = currNode.findChild(key.charAt(0));
            if (currNode == null) {
                return null;
            }
            key = key.substring(1);
        }
        return currNode.getValue();
    }
    
    /**
     * Hack-ish way to override Map<K,V>.remove(Object o) due to horrible design
     * in the Java SE library. Thanks alot, morons. If not implemented, default version
     * of Map<K, V>.remove will be used when using interface form.
     * 
     * It is deprecated so any use of the Object form on something that could use the
     * String form will give warnings.
     */
    @Deprecated
    @Override
    public E remove(Object key)
    {
    	return remove((String) key);
    }

    /**
     * Removes the key/value pair associated with the given key.
     * @param keyParameter the key to be removed from the Trie.
     * @return the value previously associated with the given key. Returns
     * null if the key was not found in the Trie.
     */
    public E remove(String keyParameter) {

        String key = keyParameter;

        /* Ignore ineligible keys */
        if (key == null || key.length() == 0) {
            return null;
        }

        Stack<N> nodeStack = new Stack<N>();

        N currNode = root;

        /* Find the node we want to remove, remembering nodes along the
        path in a Stack. */
        while (key.length() > 0) {
            nodeStack.push(currNode);
            currNode = currNode.findChild(key.charAt(0));

            /* We couldn't find the key we want to remove,
            so give up and return null */
            if (currNode == null) {
                return null;
            }

            /* Remove the first character of the key */
            key = key.substring(1);
        }

        /* Later, we'll need to return the value we're removing */
        E previousValue = currNode.getValue();

        /* Explicitly remove the value, so that the breaking condition
         * in the following loop doesn't trigger */
        currNode.setValue(null);

        char childKey;

        /* We need to remove the node containing the given key, but we also
         * need to remove its unused parent nodes */
        while (true) {
            /* Invariant: at this point, currNode is the node we are considering
             * removing from the Trie */
            childKey = currNode.getKey();

            /* Breaking conditions, we will NOT remove currNode and leave the loop
             * if any of the following conditions are true:
             * 1. currNode holds a value other than the one originally removed.
             * 2. currNode has another child.
             * 3. currNode is the root node of the Trie. */
            if (currNode.getValue() != null || !currNode.isLeaf() || currNode == root) {
                break;
            }

            /* currNode now becomes its parent. */
            currNode = nodeStack.pop();

            /* Actually remove the child from its parent. */
            currNode.removeChild(childKey);
        }

        size--;
        return previousValue;
    }

    /**
     * Calculates the total number of nodes in the
     * Trie structure, including the root node. Probably not actually useful,
     * but interesting for those looking to confirm their understanding of Tries.
     * @return the number of nodes in the internal Trie stucture.
     */
    public int getNodeCount() {
        return 1 + root.countDescendants();
    }

    /**
     * Returns how many key/value pairs exist in the Trie.
     * @return the number of key/value pairs in the Trie.
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Resets the Trie structure, removing all key/value pairs.
     */
    @Override
    public void clear() {
        root = createNode();
        size = 0;
    }

    /**
     * Returns whether or not the Trie contains any key/value mappings.
     * @return true if the Trie contains no key/value mappings. Otherwise, false.
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Overrides Object's toString method. This returns a string representation
     * of the key/value mappings in the Trie.
     * @return a string representation of the key/value mappings in the Trie.
     */
    @Override
    public String toString() {
        String result = "{";
        String keyValueList = root.toString("");
        if (keyValueList.length() > 0) {
            keyValueList = keyValueList.substring(0, keyValueList.length() - 2); //remove trailing ", "
        }
        result += keyValueList;
        result += "}";
        return result;
    }


    /**
     * Copies all of the key/value pairs from the given Map
     * into this Trie.
     * @param m the Map from which we will add keys/values.
     */
    @Override
    public void putAll(Map<? extends String, ? extends E> m) {
        if (m == null) {
            throw new NullPointerException("The Map parameter m is null.");
        }
        Set<?> entrySet = m.entrySet();
        Iterator<?> setIterator = entrySet.iterator();

        /* Iterate through the Map parameter and ensure the following are true:
        1. No keys are null.
        2. No values are null.
        3. No keys are non-Strings. */
        while (setIterator.hasNext()) {
        	@SuppressWarnings("unchecked")
            Map.Entry<String, E> entry = (Map.Entry<String, E>) setIterator.next();
            if (entry.getKey() == null) {
                throw new NullPointerException("The map cannot be added to the Trie " +
                        "because it contains a null key." +
                        "\nKey: " + entry.getKey() +
                        "\nValue: " + entry.getValue() +
                        "\nNo values from this map were added to the Trie.");
            }
            if (entry.getValue() == null) {
                throw new NullPointerException("The map cannot be added to the Trie " +
                        "because it contains a null value." +
                        "\nKey: " + entry.getKey() +
                        "\nValue: " + entry.getValue() +
                        "\nNo values from this map were added to the Trie.");
            }
            if (entry.getKey().getClass() != String.class) {
                throw new ClassCastException("The map cannot be added to the Trie " +
                        "because it contains a key which is not a String." +
                        "\nKey: " + entry.getKey() +
                        "\nValue: " + entry.getValue() +
                        "\nNo values from this map were added to the Trie.");
            }
        }

        /* If the Map contains no invalid keys/values, insert its values into
         * the Trie. */
        setIterator = entrySet.iterator();
        while (setIterator.hasNext()) {
            @SuppressWarnings("unchecked")
			Map.Entry<String, E> entry = (Map.Entry<String, E>) setIterator.next();
            put(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Returns a Set view of all keys in this Trie.
     * @return a Set containing all of the keys in this Trie.
     */
    @Override
    public Set<String> keySet() {
        return root.keySet("");
    }

    /**
     * Returns a Set view of all Leaf nodes keys in this Trie.
     * @return a Set containing all of the leaf keys in this Trie.
     */
    public Set<String> leafKeySet() {
        return root.leafKeySet("");
    }

    /**
     * Returns a Collection of all values in this Trie.
     * @return a Collection containing all of the values in this Trie.
     */
    @Override
    public Collection<E> values() {
        return root.values();
    }

    /**
     * Returns a Set view of the key/value mappings in this Trie.
     * @return a Set containing Entry objects for this Trie.
     */
    @Override
	public Set<Map.Entry<String, E>> entrySet() {
        return root.entrySet("");
    }
    
    public Set<Map.Entry<String, E>> leafEntrySet() {
        return root.leafEntrySet("");
    }

    /**
     * Inner class used to describe an individual entry in the Trie.
     * @param <String>
     * @param <E>
     */
    public static class Entry<K, V> implements Map.Entry<K, V> {

        private final transient K key;
        private transient V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
		public K getKey() {
            return key;
        }

        @Override
		public V getValue() {
            return value;
        }

        @Override
		public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
    }
}
